/**
 * 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

 

示例 1：


输入：root = [1,2,3,4,5,6]
输出：6
示例 2：

输入：root = []
输出：0
示例 3：

输入：root = [1]
输出：1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/count-complete-tree-nodes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes1 = function (root) {

    let count = 0

    const dfe = (root) => {
        if (!root) return
        count++
        root.left && dfe(root.left)
        root.right && dfe(root.right)
    }
    dfe(root)
    return count
};

var countNodes = function (root) {
    //把问题拆解成满二叉树
    if (!root) return 0

    let nodeLeft = root, nodeRight = root;

    let lth = 0;
    let rth = 0;
    while (nodeLeft) {
        lth++
        nodeLeft = nodeLeft.left
    }
    while (nodeRight) {
        rth++
        nodeRight = nodeRight.right
    }
    //如果是满二叉树
    if (lth == rth) {
        return Math.pow(2, lth) - 1
    }

    return countNodes(root.left) + countNodes(root.right) + 1

};


